package com.cty.fifthDay;
/*给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]]
满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。
请你返回所有和为 0 且不重复的三元组。注意：答案中不可以包含重复的三元组。
*/


import java.util.*;

public class Q_6 {
    public static void main(String[] args) {
        int[] nums = {-1, 0, 1, 2, -1, -4};
        List<List<Integer>> lists = threeSum2(nums);
        for (List<Integer> list : lists) {
            System.out.println(Arrays.toString(list.toArray()));
        }
    }

    //暴力解法 时间复杂度O(n^3)
    public static List<List<Integer>> threeSum(int[] nums) {
        if (nums == null && nums.length == 0) return new ArrayList<>();
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                for (int k = j + 1; k < nums.length; k++) {
                    if (nums[i] + nums[j] + nums[k] == 0) {
                        ArrayList<Integer> Integers = new ArrayList<>();
                        Integers.add(nums[i]);
                        Integers.add(nums[j]);
                        Integers.add(nums[k]);
                        //将列表排序
                        Collections.sort(Integers);
                        if (!res.contains(Integers)) {
                            res.add(Integers);
                        }
                    }
                }
            }
        }
        return res;
    }

    //双指针法
    public static List<List<Integer>> threeSum2(int[] nums) {
        if (nums == null && nums.length == 0) return new ArrayList<>();
        List<List<Integer>> ans = new ArrayList<>();
        //先将数组从小到大排序
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            //将三数之和 变为两数之和(简化)
            List<List<Integer>> search = search(nums, i + 1, nums.length-1, -nums[i]);
            ans.addAll(0,search);
        }
        return ans;
    }

    public static List<List<Integer>> search(int[] nums, int start, int end, int target) {
        List<List<Integer>> ans = new ArrayList<>();
        while (start < end) {
            //把strat的元素和end的元素的和存储起来
            int sum = nums[start] + nums[end];
            if (sum == target) {//判断两数之和与target的关系
                List<Integer> integers = new ArrayList<>();
                integers.add(nums[start]);
                integers.add(nums[end]);
                integers.add(-target);
                ans.add(integers);
                //如果符合就寻找 下一组解 有相同的元素 就继续移动指针
                while (start < end && nums[start + 1] == nums[start]) {
                    start++;
                }
                start++;
                while (start < end && nums[end] == nums[end - 1]) {
                    end--;
                }
                end--;
            } else if (target > sum) {
                // 如果sum比target小 则说明 start元素太小 要增大
                start++;
            } else {
                // 如果sum比target大 说明end元素太大 减小end元素
                end--;
            }
        }
        return ans;
    }
}
